/**
 * 
 */
package solution.tree.bfs;

import java.util.ArrayList;
import java.util.List;

import lib.tree.BNode;
import lib.tree.TreeUtil;

import org.apache.commons.lang.StringUtils;
import org.junit.Assert;
import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 */
public class AnticlockPrint {

	List<Integer> prt;

	void antiClockPrint(BNode tree) {
		if (tree == null)
			return;
		prt = new ArrayList<Integer>();
		prt.add(tree.value);
		antiClockPrintRec(tree, true, true);
	}

	void antiClockPrint2(BNode tree) {
		if (tree == null)
			return;
		prt = new ArrayList<Integer>();
		prt.add(tree.value);
		antiClockPrintRec2(tree, true, true);
	}

	/**
	 * version 1. does not print the indent nodes in 0(1(,4(9,10)),2(5(11,12),))
	 * 
	 * @param tree
	 * @param printLeft
	 * @param printRight
	 */
	void antiClockPrintRec(BNode tree, boolean printLeft, boolean printRight) {
		if (tree == null)
			return;

		if (tree.isLeaf()) {
			// print leaves. avoid printing the leftmost and rightmost leaves
			// twice.
			if (!printLeft && !printRight) {
				prt.add(tree.value);
			}
			return;
		}

		// preorder traversal for left edge
		if (printLeft && tree.left != null) {
			prt.add(tree.left.value);
		}
		antiClockPrintRec(tree.left, printLeft, false);

		// postorder traversal for right edge
		antiClockPrintRec(tree.right, false, printRight);
		if (printRight && tree.right != null) {
			prt.add(tree.right.value);
		}
	}

	/**
	 * version 2.
	 * 
	 * @param tree
	 * @param printLeft
	 * @param printRight
	 */
	void antiClockPrintRec2(BNode tree, boolean printLeft, boolean printRight) {
		if (tree == null)
			return;

		// special handing the leaves and make sure it is not printed twice.
		if (tree.isLeaf()) {
			if (!printLeft && !printRight) {
				prt.add(tree.value);
			}
			return;
		}

		// print the left child. preorder traversal.
		// if left is empty, continue on the right child
		if (printLeft) {
			if (tree.left != null) {
				prt.add(tree.left.value);
			} else {
				prt.add(tree.right.value);
			}
		}
		antiClockPrintRec2(tree.left, printLeft, printRight
				&& tree.right == null);

		antiClockPrintRec2(tree.right, printLeft && tree.left == null,
				printRight);
		// print the right child. post-order traversal.
		// if right is empty, continue on the left child
		if (printRight) {
			if (tree.right != null) {
				prt.add(tree.right.value);
			} else {
				prt.add(tree.left.value);
			}
		}
	}

	@Test
	public void test() {
		TreeUtil treeUtil = new TreeUtil();

		for (String d[] : new String[][] { //
		//
				{ "4(2(1,3),6(5,7)))", "4,2,1,3,5,7,6" },//
				{ "1(7(2,6(5,11)),8(,9(4,)))", "1,7,2,5,11,4,9,8" }, //
				{ "1(2(4(8,9),5),3(6,7))", "1,2,4,8,9,5,6,7,3" }, //
				{ "8(4(2(,3),5(,7)),12(9(,10),14))", "8,4,2,3,7,10,14,12" }, //
				{ "0(1(,4(9,10)),2(5(11,12),))", "0,1,4,9,10,11,12,5,2" }, //
		}) {
			BNode tree = treeUtil.makeTree(d[0]);
			antiClockPrint2(tree);
			String result = StringUtils.join(prt, ",");
			System.out.println(result);
			Assert.assertEquals(d[1], result);
		}
	}
}
